class Queue {
  constructor() {
    this.buf = new Array(5)
    this.start = 0
    this.end = 0
  }

  push(elem) {
    if ((this.end + 1) % this.buf.length == this.start) {
      // 队列满
      const len = this.buf.length
      this.buf.length = len * 2
      if (this.start > 0) {
        for (let i = 0; i < this.end; i++) {
          this.buf[len + i] = this.buf[i]
        }
        this.end += len
      }
    }
    this.buf[this.end] = elem
    this.end = (this.end + 1) % this.buf.length
  }

  shift() {
    if (this.start == this.end) {
      // 队列空
      return
    }
    const ret = this.buf[this.start]
    this.start = (this.start + 1) % this.buf.length
    return ret
  }
}

const usage = `Usage: node numbers.js <numbers>
numbers:
    example: 876543210 for
             8 7 6
             5 4 3
             2 1
    0 means space`

if (!process.argv[2] || process.argv[2].length != 9) {
  console.error(usage)
  return
}

const arr = []

const arrC = {}
for (const c of process.argv[2]) {
  const num = Number(c)
  if (!isFinite(num) || num < 0 || num > 9 || arrC[num]) {
    console.error(usage)
    return
  }
  arr.push(num)
  arrC[num] = true
}

const nextTable = [[1, 3], [0, 2, 4], [1, 5], [0, 4, 6], [1, 3, 5, 7], [2, 4, 8], [3, 7], [4, 6, 8], [5, 7]]
const dispTable = ['  ', ' 1', ' 2', ' 3', ' 4', ' 5', ' 6', ' 7', ' 8']
const visited = {}
let visitedCount = 0
const queue = new Queue()
queue.push({ curr: arr, currPos: arr.indexOf(0), prevPos: -1, prevStr: '' })
while (1) {
  const obj = queue.shift()
  if (!obj) {
    console.error('No solution!')
    break
  }
  const { curr, currPos, prevPos, prevStr } = obj
  const currStr = curr.join('')
  if (visited[currStr] != null) {
    continue
  }
  if (currStr == '123456780') {
    console.error(`Done! (${visitedCount} states visited)`)
    const steps = [currStr]
    let str = prevStr
    while (str) {
      steps.push(str)
      str = visited[str]
    }
    console.error(`Take ${steps.length - 1} steps`)
    for (let i = steps.length - 1; i >= 0; i--) {
      for (const c of steps[i].slice(0, 3)) process.stdout.write(dispTable[c])
      console.log('')
      for (const c of steps[i].slice(3, 6)) process.stdout.write(dispTable[c])
      console.log('')
      for (const c of steps[i].slice(6, 9)) process.stdout.write(dispTable[c])
      console.log('\n')
    }
    break
  }
  visited[currStr] = prevStr
  visitedCount++
  for (const pos of nextTable[currPos]) {
    if (pos != prevPos) {
      const next = curr.slice()
      next[currPos] = next[pos]
      next[pos] = 0
      queue.push({ curr: next, currPos: pos, prevPos: currPos, prevStr: currStr })
    }
  }
}
